#include<iostream>
#include<vector>
#include<string>
using namespace std;

struct Node{
	struct Node* word[26];
	int flag[26];
};

class MagicDictionary {
private:
	static struct Node* _root;
public:
	MagicDictionary() {
	}

	static void CreatDicTree(string& s)
	{
		struct Node* _cur = _root;
		for (int i = 0; i<s.size(); i++)
		{
			if (i != s.size() - 1)
			{
				
				_cur->word[s[i] - 'a'] = new struct Node;
				_cur->flag[s[i] - 'a'] = 1;
				_cur = _cur->word[s[i] - 'a'];
			}
			else
				_cur->flag[s[i] - 'a'] = 1;
		}
	}
	void Print()
	{
		struct Node* _cur = _root;
		while (_cur!=nullptr)
		{
			for (int i = 0; i < 26; i++)
			{
				if (_cur->flag[i] == 1)
				{
					char s = i + 97;
					cout << s;
					_cur = _cur->word[i];
					break;
				}
			}
		}
	}
	void buildDict(vector<string> dictionary) {
		for (auto x : dictionary)
		{
			CreatDicTree(x);
		}
	}

	bool search(string searchWord) {

	}
};

int main()
{
	MagicDictionary S;
	vector<string> s = { "abcde", "bcder" };
	S.buildDict(s);
	S.Print();
	return 0;
}
 struct Node*MagicDictionary::_root = new struct Node;